 We now present an algorithm for generating a random spanning
tree (RST) of an unweighted undirected network in $\tilde{O}(\sqrt{m}D)$ rounds with
high probability.  The approach is to simulate Aldous and Broder's \cite{aldous,broder}
RST algorithm  which is as follows. First, pick one arbitrary node as a root. Then, perform a random walk from the root node until
all nodes are visited. For each non-root node, output the edge that
is used for its first visit.  (That is, for each non-root node $v$,
if the first time $v$ is visited is $t$ then we output the edge $(u,v)$
where $u$ is the node visited at time $t-1$.)
%
The output edges clearly form a spanning tree and this spanning tree
is shown to come from a uniform distribution among all spanning trees of the graph~\cite{aldous,broder}.
%
The expected time of this algorithm is the expected cover time of
the graph which is shown to be $O(mD)$ (in the worst case, i.e., for any undirected, unweighted graph) by Aleniunas et
al.~\cite{aleliunas}. 
%This also implies that the cover time is $O(mD\log n) = \tilde{O}(mD)$ with high probability.

This algorithm can be simulated on the distributed network by our
random walk algorithm as follows. The algorithm can be viewed in phases. Initially, we pick a root node
arbitrarily and set $\ell=n$. In each phase, we run $\log n$ (different) walks of length
$\ell$ starting from the root node (this takes
$\tilde{O}(\sqrt{\ell D})$ rounds using our distributed random walk algorithm).  If none of the $O(\log n)$ different walks cover all nodes (this can be easily checked in $O(D)$ time), we
double the value of $\ell$ and start a new phase, i.e., perform again $\log n$  walks of length $\ell$. The algorithm continues
until one walk of length $\ell$ covers all nodes. We then use
such walk to construct a random spanning tree: As the result of this
walk, each node knows its position(s) in the walk (cf. Section~\ref{sec:analysis}), i.e., it has a list
of steps in the walk that it is visited. Therefore, each non-root
node can pick an edge that is used in its first visit by
communicating to its neighbors. Thus at the end of the algorithm,
each node can know which of its adjacent edges belong to the output tree.  (An additional $O(n)$ rounds may be
used to deliver the resulting tree to a particular node if needed.)

We now analyze the number of rounds in term of $\tau$, the expected
cover time of the input graph. The algorithm takes $O(\log\tau)$ phases
before $2\tau\leq \ell\leq 4\tau$, and since one of $\log n$ random
walks of length $2\tau$ will cover the input graph with high
probability, the algorithm will stop with $\ell\leq 4\tau$ with high
probability. Since each phase takes $\tilde{O}(\sqrt{\ell D})$ rounds, the total number of rounds is $\tilde
{O}(\sqrt{\tau D})$ with high probability.
Since  $\tau=\tilde{O}(mD)$, we have the following theorem.

\begin{theorem}
The  algorithm described above generates a uniform random spanning tree
in $\tilde O(\sqrt{m}D)$ rounds with high probability.
\end{theorem}

